T1 分段 DP
Description
给定长度为 的单调不减序列 。定义一个区间的权值为区间长度与区间最小值的乘积。求将该序列分成 段的权值和的最大值。
浅い夢だから 胸をはなれない
给定长度为 n 的单调不减序列 {a} 。定义一个区间的权值为区间长度与区间最小值的乘积。求将该序列分成 k∈[1,n] 段的权值和的最大值。
1≤n≤2×105,1≤ai≤8×103
有一棵树,初始时只有 4 个节点, 2 3 4 的父节点都是 1 。 q 次操作,每次给定一个点 u 。设操作前点数为 n ,那么本次操作就是将 n+1 和 n+2 连在 u 上。操作后输出目前树的直径大小。
q≤5×105 。
众所周知,在求解费用流的时由于要建反边,必然会有负权边的存在。所以费用流的通常写法是 EK+SPFA。
事实上我们是可以通过一些技巧,使得 dijkstra 也可以跑费用流。这样的好处是保证了复杂度的下限。
本文将探讨如何使得 dijkstra 可以跑费用流。
给定一个长度为 n 的十进制数 s 和一个质数 p 。 q 次询问,每次给定 l r ,询问有多少十进制数 s[x:y] (l≤x≤y≤r) 能被 p 整除。
1≤n,q≤2×105,p≤2×109
给定一个 n 列的表格,每列的高度 hi 各不相同,但底部对齐,然后向表格中填入 k 个相同的数,填写时要求不能有两个数在同一列。若两个数在同一行,但是中间某一列断开是被允许的,否则也不允许。求填数的方案数对 109+7 取模的值。
n≤500,hi≤106